#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void getnext(char* str,int len,int* next)
{
    next[0] = -1;
    next[1] = 0;
    int i=2;//从第三位开始，每一位要根据前一位的值来判断
    int j=0;//j两个含义，当前和i-1比的那个元素的位置，当前i-1位置在next数组中的值
    while(i<len)
    {
        if(j== -1 || str[i-1] == str[j])
            next[i++] = ++j;
        else
            j = next[j];
    }
}

int kmp(char* str1,char* str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    int* next = (int*)malloc(sizeof(int)*len2);
    getnext(str2,len2,next);
    for(int i = 0; i < len2+1; i++)
    {
        printf("%d ",next[i]);
    }

    if(len2==0||len1==0&&len2==0)
    return 0;
    if(len1 == 0||len1<len2)
    return -1;

    int i= 0;
    int j= 0;
    while(i<len1 && j<len2)
    {
        if(str1[i]==str2[j])
        {
            i++;
            j++;
        }
        else if(j>0)
        j = next[j];
        else
        i++;

        if(j == len2)
        return i-j;
    }
    return -1;
}

int main(int argc,char* argv[])
{
    char* a = "aabaacabaabacabaca";
    char* b = "abaa";

    int i = kmp(a,b);
    printf("\n%d\n",i);

    return 0;
}